import java.util.Arrays;

public class Heap {
    public int[] elements;// 底层数组
    public int usedSize;// 有效元素个数
    // 构造方法
    public Heap(){
        // 数组初始化容量
        this.elements = new int[10];
    }
     // 创建堆，获取 输入数组 的 数据
    public void creationHeap(int[] array){
        this.usedSize += array.length;
        if(isFull()){
            this.elements = Arrays.copyOf(this.elements,this.elements.length*2);
        }
        this.elements = Arrays.copyOf(array,array.length);

        for(int parent = (this.usedSize -1 - 1)/2 ;parent >= 0;parent--){
            // 向下调整
            shiftDown(parent,this.usedSize);
        }
    }
    // 向下调整
    public void shiftDown(int parent,int len){
        int child = parent * 2 + 1;// 左孩子
        // 能进入该循环，说明 这个 parent 只少有一个孩子。
        while(child < len){
            // 获取 左右孩子的最大值
            if(child+1 < len &&this.elements[child] < this.elements[child+1]){
                child++;
            }
            // 判断 孩子最大值 是否 比  双亲节点 val 值 大
            // 如果大，就需要进行交换
            if(this.elements[child] > this.elements[parent]){
                int tmp = elements[child];
                elements[child] = elements[parent];
                elements[parent] = tmp;

                // 见附图
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }

    // 入队操作
    public void offer(int val){
        if(isFull()){
            // 扩容
            this.elements = Arrays.copyOf(this.elements,this.elements.length * 2);
        }
        elements[usedSize++] = val;
        //usedSize++;
        shiftUp(usedSize-1);// 有效元素个数 是 usedSize,最后一个元素的下标是 usedSize -1
    }
    private void shiftUp(int child){
        int parent = (child - 1)/2;
        while(child > 0){
            if(this.elements[child] > this.elements[parent]){
                int tmp = this.elements[child];
                this.elements[child] = this.elements[parent];
                this.elements[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }else{
                break;
            }
        }
    }
    // 判断队列满没满
    public boolean isFull(){
        return this.usedSize >= this.elements.length;
    }

    // 出队操作
    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空！");
        }
        int tmp = this.elements[0];
        this.elements[0] = this.elements[this.usedSize -1];
        this.elements[this.usedSize - 1] = tmp;
        this.usedSize--;
        shiftDown(0,usedSize);
        return tmp;
    }

    // 判断队列 空不空
    public boolean isEmpty(){
        return this.usedSize == 0;
    }
    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空！");
        }
        return this.elements[0];
    }

    public void heapTraversal(){
        // 最后一个未排序元素的下标
        int last = this.elements.length - 1;
        while(last > 0){
            int tmp = this.elements[0];
            this.elements[0] = this.elements[last];
            this.elements[last] = tmp;
            shiftDown(0,last);
            last--;
        }
    }

}
